package tree;

/**
 * @author justnow
 * Created on 2020-10-04
 * Description
 * 二叉树的最近公共祖先
 *
 * 【祖先的定义】：若节点p在节点root的左(右)子树中，或p=root，则成root是p的祖先
 * 【最近公共祖先的定义】：设节点root为节点p，q的某公共祖先，若其左子节点和右子节点
 *  都不是p，q的公共祖先，则称root是“最近的公共祖先”
 *  若root是p，q的【最近公共祖先】，则只可能为以下情况之一：
 *      1. p和q在root的子树中，且分列root的异侧（即分别在左、右子树中）
 *      2. p = root，且q在root的左或右子树
 *      3. q = root，且p在root的左或右子树
 *
 */
public class SwardOffer68_2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 当root为null说明此时到了叶子节点，直接返回null就好了
        // 当root等于p或者q，则直接返回root节点的内容
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //当left和right同时为空：说明root的左右子树都不包含p，q，则返回null
        if (left == null && right == null) return null;
        // 当left为null，right不为空：p和q都不在root的左子树，直接返回right。具体可分为两种情况：
        //  1. p和q其中一个在root的右子树中，此时right指向p
        //  2. p和q两节点都在root的右子树中，此时right指向最近公共祖先节点
        if (left == null) return right;
        if (right == null) return left;
        //当left和right同时不为空：说明p，q分别在root的异侧（分别在左/右子树），因此root为最近公共祖先，返回root
        return root;
    }
}
